package main

import "fmt"

/*
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。
请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。

示例 1：
输入：[3,4,5,1,2]
输出：1

示例 2：
输入：[2,2,2,0,1]
输出：0
*/

//二分
//数组中的最后一个元素x：在最小值右侧的元素，它们的值一定都小于等于x；而在最小值左侧的元素，它们的值一定都大于等于x。

func minArray(numbers []int) int {
	var (
		n     = numbers
		left  = 0
		right = len(n) - 1
	)
	for left < right {
		mid := (right + left) / 2
		if n[mid] > n[right] {
			//n[mid]是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分
			left = mid + 1
		} else if n[mid] < n[right] {
			//n[mid]是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分
			right = mid
		} else {
			//若 n[mid] == n[right] 可能会有两个相等的最小值 忽略右侧端点
			right--
		}
	}
	return n[left] //此时左侧点为最小值
}

//暴力
/*
func minArray(numbers []int) int {
	var (
		left  = 0
		right = 1
		L     = len(numbers)
		n     = numbers
	)
	for right < L {
		if n[left] > n[right] {
			break
		} else {
			left++
			right++
		}
	}
	if right == len(n) {
		return n[0]
	}
	return n[right]
}
*/

func main() {
	nums := []int{3, 1, 3}
	fmt.Println(minArray(nums))
}
